1. Field of Invention
This invention relates to the preparation for efficient and precise evaluation of polynomial functions for numerical evaluation and analysis, and, particularly, polynomials evaluated with floating point, or similar, operations, in hardware or software, within a general purpose computer or numerical processor.
2. Discussion of Prior Art
The basic functionality embodied in differencing a real value and x, an exact floating point number, as in x±realValue is equivalent to the evaluation of a first degree primitive polynomial, as defined by (x−realRoot). Yet, the literature on polynomial evaluation does not show any way to consistently and quickly setup and perform a precise evaluation of the simple (x−realRoot) expression. This absence was the motivating factor to seek patent protection. By “precise”, it is meant that the relative precision of the result reflects the number of bits of precision.
In addition to linear terms, as in (x−realRoot), a conjugate term, such as in (x^2+c), is needed for efficient evaluation of polynomials using a root product form. Although, these forms require some refinement, they can be combined as a product of such factors.
The closest prior art is found in the Root Product form, described below, as item 4 in the section called Polynomial Approaches.
Basic Differencing Operation: x±rReal
Considerable literature exists on computing adds and subtracts with floating point operations, including multiple precision within floating point environments. The literature does not indicate any methods which work for all cases, other than the possibly unlimited increase in the precision of both the numeric representations and arithmetic operators, as needed, to provide the desired relative precision after massive cancellation of digits.
In traditional methods of differencing of an arbitrary real value and exact floating point input to produce a specific relative precision, there is no limit to the amount of precision required for the input real value. Problems arise whenever the real value approaches close to the exact input floating point value and thereby causes massive cancellation of significant digits.
Polynomial Approaches
Real polynomials can be expressed in many forms and each form has various methods of evaluation. Currently, there appears to be several commonly used methods: direct evaluation methods based on the polynomial specification; elegant and efficient methods which are fast but lack guaranteed precision for the general case; and brute force methods which attempt to produce a precise result using whatever computational resources are required. Current methods can be fast and can sometimes succeed with finite resources. However, these methods are sometimes inadequate for many applications and explains why polynomial processing is often avoided.
1. Direct Specification Approach
A polynomial can be evaluated based on its definition. For example, “3+2*x^1−5*x^2”, can be directly evaluated for x. Indeed, the above expression can be input to a computer language compiler to produce computer instruction codes. However, these direct specification methods, even with exact numeric coefficients, do not always produce precise results, due to digit cancellation, when used directly with floating point processing.
2. Fast or Elegant Evaluation
Polynomials can be put into alternative forms that require fewer instructions. For example, use of Horner's Rule or the myriad methods in the Knuth reference [4]. Although faster, these methods are precise by accident. Because of their efficiency, and because they sometimes maintain adequate precision over a required input domain, they appear to be the mainstay of numeric processing on the computer.
3. Precise Brute Force Evaluators
For programs which must return a precise answer for an evaluation, such as a solution requirement for a specific number of correct significant digits, the simplest traditional approach is typically used: choose one of the above methods and iterate to a precise solution by raising the precision of the input and all internal expression evaluations until a sufficiently precise result is obtained as the final result. To avoid an apparent computational “freeze”, the program sometimes has a method to detect when computer resources are insufficient or too much time has elapsed.
In addition to actual evaluation and resource checking, the program must, in some fashion, keep track of error intervals in order to determine successful completion of the iteration. Whether using intervals or other means, these additional calculations can easily double the computation time.
4. Root Product Form:
The theoretical evaluation of a real polynomial in root-product form is well-known for a degree n polynomial with n number of roots. It consists of the product of the lead factor times terms consisting of (x−r) and terms consisting of ((x−r) ^2+c).
Unlimited Precision Requirements
The above root products are simple to evaluate and lead to very simple and tight error bounds when the roots are exactly representable in the floating point form. (See the Higham book, page 115, exercise 5.5, and answers to exercises). However, on a computer, the subtraction of (x−root[i]), wherein the root is usually approximated, can easily suffer catastrophic digit cancellation, rendering an imprecise result. In order that the result of (x−r) be precise, the amount of precision required for the approximated root is theoretically unlimited.
Exponent Overflow and Underflow
Exponent overflow and underflow is another very serious problem with the root product form. The root parts of the polynomial may have exponent ranges which lie far outside the range of hardware floating point; this may occur even when the overall input domain and output values are well within the range of exponents. Extreme exponents for the roots also leads to intermediate values which are outside the range of allowed exponents.